import java.util.*;

// 链表分割

 class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        if(pHead==null){
            return pHead;
        }

        //创建两个虚拟结点
        //一个用来存放小于x的结点
        //一个用来存放大于等于x的结点
        ListNode newh1=new ListNode(-1);
        ListNode newh2=new ListNode(-1);

        //创建临时节点
        ListNode temp1=newh1;
        ListNode temp2=newh2;

        ListNode cur = pHead;

        while(cur!=null){
            if(cur.val<x){
                temp1.next=cur;
                temp1=temp1.next;
            }else{
                temp2.next=cur;
                temp2=temp2.next;
            }
            cur=cur.next;
        }

        //注意要把链表尾置空,如果没有置空则说明链表尾没有断开
        //没有置空可能发生的问题:
        /*链表循环或环：链表未正确处理尾节点（例如未将 temp2.next 设为 null）
        ，导致链表形成环。这样打印或操作链表时会陷入无限循环，消耗大量内存。*/
        temp2.next = null;
        //链表1接上链表2
        temp1.next = newh2.next;
        return newh1.next;
    }
}